package com.order.www;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定两个字符串S和T，返回S子序列等于T的不同子序列个数有多少个？
 * 字符串的子序列是由原来的字符串删除一些字符（也可以不删除）在不改变相对位置的情况下的剩余字符（例如，"ACE"is a subsequence of"ABCDE"但是"AEC"不是）
 * 例如：
 * S="nowcccoder", T = "nowccoder"
 * 返回3
 * User:yxd
 * Date:2022-03-23
 * Time:22:32
 */
public class Dp10 {
    public int numDistinct (String S, String T) {
        // write code here
        //状态定义：F(i,j) i个字符包含j个字符的不同序列数
        //状态转移方程： F(i,j) : 首先要看第i和第j字符相不相等
        //如果相等的话 可以选择 不用第这个字符 就直接回退到F(i - 1,j - 1)
        //如果选择使用这个字符那就是F(i - 1,j)
        //如果不相等的话 就不能使用第i个字符 直接回退到F(i - 1,j)
        //初值：第一列每一个字符串都可以拼接空串因此都为1
        //第一行除第一个外空串不能和任何字符相等都为0
        if(S == null || T == null){
            return -1;
        }
        int n = S.length();
        int m = T.length();
        /*int[][] dp = new int[n + 1][m + 1];
        for(int i = 1;i <= m;i ++){
            dp[0][i] = 0;
        }
        for(int i = 0;i <= n;i ++){
            dp[i][0] = 1;
        }
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                //S第i个字符和T第j个字符相等
                if(S.charAt(i - 1) == T.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][m];*/
        int[] dp = new int[m + 1];
        dp[0] = 1;
        for(int i = 1;i <= n;i ++){
            for(int j = m;j > 0;j --){//要先使用未更新的值所以必须从后往前更新保证使用的是上一行的值而不是这一行已经更新过的值
                if(S.charAt(i - 1) == T.charAt(j - 1)){
                    dp[j] = dp[j - 1] + dp[j];
                }
            }
        }
        return dp[m];
    }
}
